﻿// 4220. 质数路径.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//

#include <iostream>
#include <set>
#include <queue>
#include <vector>
#include <cstring>

using namespace std;
/*
* https://www.acwing.com/problem/content/description/4223/
给定两个四位质数 A 和 B，你需要通过最少的操作次数将 A变为 B。

每次操作只能改变当前数的其中一位数字，并且每次操作过后，当前数必须仍然是一个质数。

例如，将 1033 变为 8179，最少需要进行 6次操作，具体操作为：

1033 -> 1733 -> 3733 -> 3739 -> 3779 -> 8779 -> 8179
请计算并输出所需要的最少操作次数。

输入格式
第一行包含整数 T，表示共有 T组测试数据。

每组数据占一行，包含两个四位质数 A和 B。

输出格式
每组数据输出一行答案，表示所需最少操作次数。

如果无法做到，则输出 Impossible。

经实际测试，不存在无解情况，特此声明。

数据范围
1≤T≤100。
1000≤A,B≤9999，
保证 A和 B 都是质数。

输入样例：
3
1033 8179
1373 8017
1033 1033
输出样例：
6
7
0
*/

const int N = 10010;
int primes[N], cnt;     // primes[]存储所有素数
bool st[N];         // st[x]存储x是否被筛掉
set<int> ss;
set<int> vis;

void get_primes(int n)
{
    for (int i = 2; i <= n; i++)
    {
        if (!st[i]) { 
            if (i > 999 && i < 9999){ss.insert(i);}
            primes[cnt++] = i; 
        }
        for (int j = 0; primes[j] <= n / i; j++)
        {
            st[primes[j] * i] = true;
            if (i % primes[j] == 0) break;
        }
    }
}

int n;
int source, target;

void change(queue<vector<int > >& q, int curr, int t,int step) {
    for (int i = 1; i < 10; i++) {
        int v = curr % (t * 10) / t;
        if (v - i >= 0 && ss.count(curr - i * t) != 0 && vis.count(curr - i * t) == 0) {
            vis.insert(curr - i * t);
            vector<int> v; v.push_back(curr - i * t); v.push_back(step + 1);
            q.push(v);
        }

        if (v + i < 10 && ss.count(curr + i * t) != 0 && vis.count(curr + i * t) == 0) {
            vis.insert(curr + i * t);
            vector<int> v; v.push_back(curr + i * t); v.push_back(step + 1);
            q.push(v);
        }
    }
}


void solve() {
    vis.clear();
    queue<vector<int > > q;
    vector<int> v; v.push_back(source); v.push_back(0);
    q.push(v); vis.insert(source);

    while (!q.empty()) {
        int curr = q.front()[0];
        int step = q.front()[1]; q.pop();
        
        if (curr == target) {
            cout << step << endl; return;
        }

        change(q,curr, 1, step);
        change(q,curr, 10, step);
        change(q,curr, 100, step);
        change(q,curr, 1000, step);
    }
    cout << "Impossible" << endl;
    return;
}


int main()
{
    get_primes(10010);

    cin >> n;
    while (n--) {
        cin >> source >> target;
        solve();
    }
}

 